#include <stdio.h>
struct node{
    int value;
    struct node *next;
};

struct node * dividesort(struct node* h){
    
    //h不存储值，而l1、l2存储值
    struct node *l1=NULL,*l2=NULL,*tail1,*tail2,*current=h;
    while(current->next!=NULL){
        current=current->next;
        if (current->value%2==1){
            if (l1==NULL){
                l1=current;
                tail1=l1;
            } else {
                tail1->next=current;
                tail1=current;
            }
        }
        else {
            if (l2==NULL){
                l2=current;
                tail2=l2;
            } else {
                tail2->next=current;
                tail2=current;
            }
        }
    }
    if (l1!=NULL)l1=sort(l1);
    if (l2!=NULL)l2=sort(l2);
    if (l1==NULL){
        h->next=l2;
        return h;
    }
    tail1=l1;
    while (tail1->next!=NULL){
        tail1=tail1->next;
    }
    h->next=l1;
    tail1->next=l2;
    return h;
}

struct node *sort(struct node *l){
    if (l==NULL)return NULL;
    while (1){
        int tag=1;
        struct node *current=l,*left=NULL,*right=current->next;
        while (right!=NULL){
            if (current->value>right->value){
                tag=0;
                if(left!=NULL)left->next=right;
                current->next=right->next;
                right->next=current;
                current=right;
                right=right->next;
            }
            left=current;
            current=current->next;
            right=right->next;
        }
        if(tag==1) break;
    }
    return l;
}
